#pragma once

#include  "iostream"
#include  "vector"
#include  "stack"
#include  "unordered_map"
#include   "queue"

using namespace std;


/*
 * 输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：6
解释：最大矩形如上图所示。
示例 2：

输入：matrix = []
输出：0
示例 3：

输入：matrix = [["0"]]
输出：0
示例 4：

输入：matrix = [["1"]]
输出：1
示例 5：

输入：matrix = [["0","0"]]
输出：0
 *
 * */

int calcMaxV(vector<int> &res) {
    stack<int> st;//确定单调站的元素是否递增
    res.push_back(-1);//我这个似乎跟别人写的不一样 我这个每次都得push一个垃圾数据 todo 要看看看区别了
    int ret = 0;
    for (int i = 0; i < res.size(); ++i) {

        if (st.empty()) {
            st.push(i);//直接push下标
        } else {
            //递增
            while (!st.empty() && res[i] < res[st.top()]) {
                int left = 0;
                int right = i;
                int h = res[st.top()];
                st.pop();
                if (st.empty()) {
                    ret = max(ret, (right - left) * h);
                } else {
                    left = st.top();
                    ret = max(ret, (right - left - 1) * h);
                }

            }

            st.push(i);

        }


    }

    //如果栈里面还有空间 比如递增这种 1 2 3 4
    int size = 0;
    int h = 0;
    while (!st.empty()) {
        if (res[st.top()] != 0) {
            h = res[st.top()];
            size++;
        }
        st.pop();
    }

    if (size > 0) {
        ret = max(ret, (h * size));
    }

    return ret;
}

//todo 按照行分 列从0开始  把这个分为那个柱状图然后求最大矩形面积就行
int maximalRectangle(vector<vector<char>> &matrix) {
    int ans = 0;
    int row = matrix.size();
    int col = matrix[0].size();
    vector<int> res;

    for (int i = 0; i < row; ++i) {
        for (int j = 0; j < col; ++j) {
            //计算高度
            if (matrix[i][j] == '0') {
                res.push_back(0);
                continue;
            } else {
                //否则就计算高度 从低向上计算不是0的数
                int t = i;
                int count = 0;
                while (t >= 0 && matrix[t][j] != '0') {
                    count++;
                    t--;
                }
                res.push_back(count);
            }
        }

        //计算最大值 清楚数组;
        ans = max(ans, calcMaxV(res));
        res.clear();
    }


    return ans;
}